dp[i][j]=min(dp[i−1][k]+(Sumj−Sumk)2) (0≤k<j)
dp[i][j]=min(dp[i−1][k]+Sumj2+Sumk2−2SumiSumk) (0≤k<j)
dp[i][j]=min(dp[i−1][k]+Sumk2−2SumiSumk)+Sumj2 (0≤k<j)
dp[i−1][j]+Sumj2−2SumiSumj<dp[i−1][k]+Sumk2−2SumiSumk
(Sumj−Sumk)(dp[i−1][j]+Sumj2)−(dp[i−1][k]+Sumk2)>2Sumi
#include <cstdio>
const int MAXN = 3000;
int n , m , Sum[ MAXN + 5 ];
int dp[ MAXN + 5 ][ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;
int deltax( int i , int j ) { return Sum[ i ] - Sum[ j ]; }
int deltay( int k , int i , int j ) { return dp[ k - 1 ][ i ] + Sum[ i ] * Sum[ i ] - dp[ k - 1 ][ j ] - Sum[ j ] * Sum[ j ]; }
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&Sum[ i ]) , Sum[ i ] += Sum[ i - 1 ];
for( int i = 1 ; i <= n ; i ++ ) dp[ 1 ][ i ] = Sum[ i ] * Sum[ i ];
for( int i = 2 ; i <= m ; i ++ ) {
Head = 1 , Tail = 0;
for( int j = 1 ; j <= n ; j ++ ) {
for( ; Head < Tail && deltay( i , Que[ Head ] , Que[ Head + 1 ] ) >= 2 * Sum[ j ] * deltax( Que[ Head ] , Que[ Head + 1 ] ) ; Head ++ );
dp[ i ][ j ] = dp[ i - 1 ][ Que[ Head ] ] + ( Sum[ j ] - Sum[ Que[ Head ] ] ) * ( Sum[ j ] - Sum[ Que[ Head ] ] );
for( ; Head < Tail && deltay( i , Que[ Tail - 1 ] , Que[ Tail ] ) * deltax( Que[ Tail ] , j ) >= deltay( i , Que[ Tail ] , j ) * deltax( Que[ Tail - 1 ] , Que[ Tail ] ) ; Tail -- );
Que[ ++ Tail ] = j;
}
}
printf("%d\n", m * dp[ m ][ n ] - Sum[ n ] * Sum[ n ] );
return 0;
}
